三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意：

  • 答案中不可以包含重复的三元组。

示例：

1
2
3
4
5
6
7
给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

代码：

7%17%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ls=new ArrayList<List<Integer>>();
        if(nums==null||nums.length<3)return ls;
        Arrays.sort(nums);
        Set<List<Integer>> set=new HashSet<List<Integer>>();
        //用于标记0，0，0是否出现
        int flag=0;
        for(int i=0;i<nums.length-2;i++)
        {
            //如果第一个就大于0了，不需要循环了
            if(nums[i]>0)break;
            //这个是第三个数的锚定点，因为j增大，k肯定要变小的
            int M=nums.length-1;
            for(int j=i+1;j<nums.length-1;j++)
            {
                if(nums[i]==0&&flag==1)break;
                else if(nums[i]==0&&nums[j]==0&&flag==0)flag=1;
                //快速移动i
                if(nums[i]==nums[j]&&nums[i]!=0)
                {
                    while(nums[i]==nums[j])
                    {
                        i = j;
                        j++;
                        if(j>= nums.length-1)break;
                    }
                    j--;
                }


                //已经大于0了，后面的这个循环不用找了
                if(nums[i] + nums[j]>0)break;

                for(int k=M;k>j;k--)
                {
                    //快速移动ijk
                    if(nums[j]==nums[k])j=k;
                    if(nums[i]==nums[k])i=k;

                    //如果第3个就还小于0了，跳过了
                    if(nums[k]<0)break;
                    //已经小于0了，后面的这个循环不用找了
                    if(nums[i] + nums[j]+nums[k]<0)break;

                    if (nums[i] + nums[j]+nums[k]==0)
                    {
                        M=k;
                        List<Integer> lstemp=new ArrayList<Integer>();
                        lstemp.add(nums[i]);
                        lstemp.add(nums[j]);
                        lstemp.add(nums[k]);
                        set.add(lstemp);
                        break;
                    }

                }
            }
        }
        ls=new ArrayList<List<Integer>>(set);
        return ls;
    }
}